"""
=================================================
@Author: Zhenzhou Liu
@Date: 2024-08-28
@Description：
==================================================
"""
from collections import deque
from typing import List


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])

        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    count = count + 1
                    grid[i][j] = "0"
                    queue = deque([(i, j)])
                    while queue:
                        ni, nj = queue.popleft()
                        if ni - 1 >= 0 and grid[ni - 1][nj] == "1":
                            queue.append((ni -1, nj))
                            grid[ni - 1][nj] = "0"
                        if nj - 1 >= 0 and grid[ni][nj - 1] == "1":
                            queue.append((ni, nj -1))
                            grid[ni][nj -1] = "0"
                        if ni + 1 < m and grid[ni + 1][nj] == "1":
                            queue.append((ni + 1, nj))
                            grid[ni + 1][nj] = "0"
                        if nj + 1 < n and grid[ni][nj + 1] == "1":
                            queue.append((ni, nj + 1))
                            grid[ni][nj + 1] = "0"
        return count

    def numEnclaves(self, grid: List[List[int]]) -> int:
        queue = deque([])
        m , n = len(grid), len(grid[0])
        for i in range(m):
            if grid[i][0] == 1:
                grid[i][0] = 0
                queue.append((i, 0))
            if grid[i][n - 1] == 1:
                grid[i][n - 1] = 0
                queue.append((i, n - 1))

        for j in range(1, n - 1):
            if grid[0][j] == 1:
                grid[0][j] = 0
                queue.append((0, j))
            if grid[m - 1][j] == 1:
                grid[m - 1][j] = 1
                queue.append((m - 1, j))
        directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                    grid[nx][ny] = 0
                    queue.append((nx, ny))

        enclaveCount = 0
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if grid[i][j] == 1:
                    enclaveCount += 1

        return enclaveCount
